package de.uniLuebeck.tcs.algorithmics;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;


public class Sudoku extends BacktrackingSkeletton<SudokuInstance, SudokuInstance>{

	enum	LoadingSteps {readName, readSize, readFields, readDone};
	
	private boolean	isComment(String line) {
		return	line.startsWith(">");
	}
	
	@Override
	protected SudokuInstance readNewInstance(BufferedReader reader) throws IOException {
		
		int[] 		intArray = null;
		String		sudokuName = "";
		String 		aktuelleZeile;
		int			sudokuSize = 0;
		int			colCounter = 0;
		LoadingSteps	step = LoadingSteps.readName;
		boolean		lineParsedCorrectly = false;
		
		//	1. Suche Zeile, die kein Kommentar ist
		//	2. Zeile darf nicht leer sein -> Name
		//	3. Naechste Zeile darf weder Kommentar noch leer sein -> groesse
		//		-> wenn doch, beginne bei 1
		//	4. Finde groesse^2 Zahlen
		
		aktuelleZeile = reader.readLine();
		while((step != LoadingSteps.readDone) && (null != aktuelleZeile)) {
			aktuelleZeile = aktuelleZeile.trim();
			switch (step) {
				case readName:
					if(!isComment(aktuelleZeile)) {
						// Namen suchen
						sudokuName = aktuelleZeile;
						step = LoadingSteps.readSize;
						lineParsedCorrectly = true;
					} else {
						step = LoadingSteps.readName;
						lineParsedCorrectly = true;
					}
					break;
				case readSize:
					if(!isComment(aktuelleZeile)) {
						// Versuche Groesse zu lesen...
						try{
							sudokuSize = Integer.parseInt(aktuelleZeile);
							step = LoadingSteps.readFields;
							intArray = new int[sudokuSize * sudokuSize];
							colCounter = 0;
							lineParsedCorrectly = true;
						} catch (NumberFormatException ex) {
							// ...falls das fehlschlaegt, suche wieder den Namen
							step = LoadingSteps.readName;
							lineParsedCorrectly = false;
						}
					} else {
						step = LoadingSteps.readName;
					}
					break;
				case readFields:
					if(!isComment(aktuelleZeile)) {
						// Versuche die Felder auszulesen...
						StringTokenizer tokenizer = new StringTokenizer(aktuelleZeile, " ");
						while(tokenizer.hasMoreTokens()) {
							String	currentToken = tokenizer.nextToken();
							if(currentToken.toLowerCase().startsWith("x")) {
								// ...'(x|X)' Zeigt ein ungesetztes Feld an
								intArray[colCounter] = 0;
								colCounter++;
							} else {
								// ...eine Zahl zeigt den Feldwert an
								try {
									intArray[colCounter] = Integer.parseInt(currentToken);
									colCounter++;
									lineParsedCorrectly = true;
								} catch(NumberFormatException ex) {
									// Bei jeglichem Lesefehler versuche das naechste Sudoku auszulesen
									step = LoadingSteps.readName;
									lineParsedCorrectly = false;
									break;
								}
							}
							
							if(colCounter >= intArray.length) {
								// Ende, wenn alle Felder gelesen wurden.
								step = LoadingSteps.readDone;
								lineParsedCorrectly = true;
							}
						}
					} else {
						// Bei jeglichem Fehler, versuche das naechste Sudoku auszulesen
						step = LoadingSteps.readName;
						lineParsedCorrectly = false;
					}
					break;
			}
			
			if(lineParsedCorrectly) {
				aktuelleZeile = reader.readLine();
				lineParsedCorrectly = false;
			}
		}
		
		return new SudokuInstance(intArray, sudokuName);
	}

	@Override
	protected Iterator<SudokuInstance> computeExtensions(int l, List<SudokuInstance> x,
			SudokuInstance instance) {
		
		
		List<SudokuInstance>	extensions = new ArrayList<SudokuInstance>();
		
		SudokuInstance	lastExtension = new SudokuInstance(instance);
		if(!x.isEmpty()) {
			lastExtension = x.get(x.size() - 1);
		}
		
		int[][] f = lastExtension.getNext();
		if(0 <= f[0][0]) {
			for(int i = 0; i < f[1].length; i++) {
				SudokuInstance	newInstance = new SudokuInstance(lastExtension);
				newInstance.setField(f[0][0], f[1][i]);
				
				extensions.add(newInstance);
			}
		}
		
		return	extensions.iterator();
	}

	@Override
	protected double getValue(int l, List<SudokuInstance> x, SudokuInstance instance) {
		SudokuInstance	xx = x.get(x.size() - 1);
		int	value = xx.getNumberOfFields() - xx.getNumberOfOpenFields();
		
		/*
		 * Falls alle Felder gesetzt wurden, und die Loesung korrekt ist, haben wir ein Optimum gefunden -> Abbruch
		 */
		if((value == xx.getNumberOfFields()) && xx.isFeasible()) {
			setInterrupted();
		}
		
		return	value;
	}

	@Override
	protected boolean isFeasibleSolution(int l, List<SudokuInstance> x,
			SudokuInstance instance) {
		/*
		 * Wrapper, der die Aufgabe an die SudokuInstance weiterleitet
		 */
		if(x.isEmpty()) {
			return	false;
		} else {
			return	x.get(x.size() - 1).isFeasible();
		}
	}

	@Override
	public void printSolution(Writer output, SudokuInstance instance)
	throws IOException {
		int sudoku_groesse = instance.getNumberOfRows();
		SudokuInstance	opt;
		
		if (null != xOpt){
			opt = xOpt.get(xOpt.size() - 1);
		}
		else{
			opt = instance;
		}
		
		String outString = instance.getSudokuName() + "\n";
		outString += (opt.getNumberOfInitialOpenFields() - opt.getNumberOfOpenFields()) + "\n";
		for(int i = 0; i < sudoku_groesse; i++){
			for(int j = 0; j < sudoku_groesse; j++){
				int feld_wert = opt.getField(i, j);
				outString += feld_wert + " ";
			}
			outString += "\n";
		}

		/*
		 * Das Ergebnis in die Ausgabe schreiben.
		 */
		output.write(outString);
	}
	
	@Override
	public String getAuthor() {
		return "Ronny Biemann, Marc Hallmann, Fabian Kausche, Andreas Maier";
	}
}
